package sort.test4_7;

public class HeapSort {

    public   int[] heapSort(int[] nums){
        if (nums.length==0){
            return null;
        }
//  CKG TODO 2023/4/7:  找到第一个非叶子节点以后  然后不断向前查找  比较
//        for (int i = nums.length/2-1; i < nums.length ; i++) {
//            adjustHeap(nums,i, nums.length);
//        }
        for (int i = nums.length/2-1; i >=0 ; i--) {
            adjustHeap(nums,i, nums.length);
        }

        for (int i= nums.length-1; i >0 ; i--) {
            int temp=nums[i];
            nums[i]=nums[0];
            nums[0]=temp;
            adjustHeap(nums,0,i);
        }

        return nums;

    }


    public  void   adjustHeap(int[] nums,int i,int length){
        int temp=nums[i];
        for (int k = 2*i+1; k <length ; k=2*k+1) {
            if (k+1<length&&nums[k]<nums[k+1]){
                k++;
            }
            if (nums[k]>temp){
                nums[i]=nums[k];
                i=k;
            }else {
                break;
            }
        }
        nums[i]=temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] a={1,5,3,9,4,7};
        heapSort.heapSort(a);
        for (int b: a
        ) {
            System.out.println(b);

        }



    }





}
